package th.retrofit.lib;

import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/powx-n/
 * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）
 */
public class Solution50 {

    public double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n == 1) return x;
        if (x == 0) return 0d;
        Map<Integer, Double> counted = new LinkedHashMap<>();
        counted.put(0, 1d);
        counted.put(1, x);
        double result = 0;
        int index = 1;
        int remain = Math.abs(n);
        while (index * 2 <= remain) {
            int next = 2 * index;
            counted.put(next, counted.get(index) * counted.get(index));
            index = next;
        }
        remain -= index;
        result = counted.get(index);
        index /= 2;
        while (remain > 0) {
            while (remain < index) {
                index = index / 2;
            }
            result *= counted.get(index);
            remain -= index;
        }
        return (double) (n > 0 ? result : 1 / result);
    }

    public double myPow1(double x, int n) {
        return n >= 0 ? quickMul1(x, n) : 1d / quickMul1(x, -n);
    }

    // 快速幂算法(迭代)
    private double quickMul1(double x, int n) {
        if (n == 0) return 1d;
        double temp = quickMul1(x, n / 2);
        return (n & 1) == 0 ? temp * temp : temp * temp * x;
    }

    public double myPow2(double x, int n) {
        return n >= 0 ? quickMul2(x, n) : 1d / quickMul2(x, -n);
    }

    private double quickMul2(double x, int n) {
        if (n == 0) return 1d;
        double result = 1.0;
        while (n > 0) {
            if ((n & 1) == 1) {
                result *= x;
            }
            x *= x;
            n = n / 2;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(new Solution50().myPow2(2d, 4));
    }

}
